Various data compression procedures have been developed to reduce the size of a particular collection of data. By reducing the size of a collection of data, the storage requirements for the data are reduced. Similarly, compressing data allows data to be transmitted more efficiently in situations where transmission bandwidth is restricted. Some data compression procedures are "lossless" while others are "lossy". A lossless compression procedure ensures that, when the compressed data is uncompressed, the uncompressed data is identical to the original data. Lossless compression procedures are often used with text streams and other data streams that cannot suffer a loss of data. A lossy compression procedure may sacrifice a portion of the original data in exchange for a better rate of compression. Lossy compression procedures are useful in situations where a slight degradation of the data will not significantly change the usefulness of the data. Lossy compression procedures are often used to compress pictures and sound.
An existing data compression procedure is referred to as run-length encoding. Run-length encoding converts a string of identical characters into a single code element. Using the run-length encoding procedure, the string "A B C C C C C C C A C B A" would be compressed to "A B !7C A C B A", where "!7C" represents the code for a string of seven "C" characters.
Another existing data compression procedure is commonly referred to as the Lempel-Ziv (LZ) technique. The basic LZ technique replaces an occurrence of a particular phrase or sequence of bytes in a set of data with a reference to a previous instance of the phrase or sequence. Thus, a phrase or sequence is replaced by a reference to an earlier part of the data stream. The basic LZ technique is illustrated with the following example. The phrase: The Yabba Dabba Show is replaced with: T, h, e, &lt;space&gt;, Y, a, b, b, a, &lt;space&gt;, D, &lt;6,5&gt;, S, h, o, w Where &lt;space&gt;indicates a single space and &lt;6,5&gt;represents the code for position 6, length 5 (i.e., the 5-character string beginning at position 6 (the first "a" in "Yabba")).
Existing data compression procedures analyze a data stream or other collection of data without reordering or rearranging the original data. Additionally, existing data compression procedures do not generally analyze the data stream or other collection of data to identify data elements that change infrequently or that change incrementally.
It is therefore desirable to provide a data compression system that takes advantage of relationships between multiple data elements in a collection of data and reorders the data based on those relationships prior to compressing the data.